#include<vector>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        srand(time(NULL));
        quicksort(arr,0,arr.size()-1,k);
        return {arr.begin(),arr.begin()+k};
    }
    void quicksort(vector<int>& arr,int left ,int right ,int k){
        //数组分三块
        if(left >= right)   return;
        int l =left-1,r = right+1,i = left;
        int key = getkey(arr,left,right);
        while(i < r){
            if(arr[i] < key)    swap(arr[++l],arr[i++]);
            else if(arr[i] == key)  ++i;
            else swap(arr[--r],arr[i]);
        }
        int a = l-left+1,b=r-l-1;
        if(a >= k)  quicksort(arr,left,l,k);
        else if(a+b >= k)   return;
        else  quicksort(arr,r,right,k-a-b);
    }
    int getkey(vector<int>& arr,int left,int right){
        return arr[rand()%(right-left+1)+left];
    }
};